// easy

// 给定一个二叉树，找出其最小深度
// 最小深度是从根节点到最近叶子节点的最短路径上的节点数量

// 解题思路:深度优先搜索递归遍历左右子树,记录最小深度
// 对于每个非叶子节点,计算其左右子树的最小叶子节点深度,将较小的深度加1即为当前节点的最小叶子节点深度

function minDepth(root) {
    // 遍历到空节点，直接返回0
    if (!root) {
        return 0
    }
    if (!root.left && !root.right) {
        return 1
    }
    let leftHeight = minDepth(root.left)
    let rightHeight = minDepth(root.right)

    // 当前节点的左右子树的最小叶子节点深度
    let min_depth = Infinity
    if (root.left) {
        min_depth = Math.min(leftHeight, min_depth)
    }
    if (root.right) {
        min_depth = Math.min(rightHeight, min_depth)
    }
    return min_depth + 1
}

const root = {
    val: "A",
    left: {
        val: "B",
        left: {
            val: "D",
        },
        right: {
            val: "E",
        },
    },
    right: {
        val: "C",
    },
};

console.log(minDepth(root));